package com.Algorithm.Study.ThinkTest;

import com.TempletGenerate.IntNumGenerate;

import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2021/10/08/9:20
 * @Description: 利用随机位于末位进行交换,再进而递归树,对于叶子节点之上的进行求中间(左右指针法)
 *              需要:1.单次的排序--如Target已经定好,那么先排一次,左边< ,右边>
 * @Target: 快速排序3.0  明白快排是如何有序的,它通过荷兰国旗的方式,每次确保中间的一个是位于中间的,,由中间不断扩展,各种中间有值
 */
public class quickSortTest {

    // 定: 先写大!递归整体,中途缺少补啥

    // [L,R]
    public static void quickProcess(int arr[],int L,int R){
        // 终止,叶子节点 L>=R终止遍历
        if(L<R){
            // 需要一直不断交换末位数的方法
            // 发现还需要一个随机数方法,随机数怎么随机整个数组?下标在随机范围就行
            swap(arr,(L + (int)(Math.random()*(R-L+1))),R);

            // 至于末位换到中间前一位,因为是每次枝节点执行的,那么写在枝中
            // 中分二叉树
            // 需要依据中间值,先求中间值
            int[] partition = partition(arr, L, R);
            quickProcess(arr,L,partition[0]-1);  // <区
            quickProcess(arr,partition[1]+1,R); // >区

        }
    }

    // 先思考左右指针求值问题,单层即可
    public static int[] partition(int arr[],int L,int R){
        int i = L;  // arr指针
        int less = L-1;  // 左边界
        int more = R;  // 右边界
        // 目标数
        int target = arr[R];
        // 1,10,13,17,6
        while (i<more){  // 循环条件,如果i>more ---表明已经循环完了
            if(arr[i]<target){
                swap(arr,++less,i++);
            }else if(arr[i]>target){
                swap(arr,--more,i);   // 换过来有可能还是大的,所以i不加
            }else {
                i++;
            }
        }
        swap(arr,more,R);

        // 1.边界与末尾交换,2.如何返回边界值,

        return new int[]{less+1,more};
    }


    public static void swap(int arr[],int i,int j){
        int m = arr[i];
        arr[i] = arr[j];
        arr[j] = m;
    }


    public static void main(String[] args) {
        IntNumGenerate intNumGenerate = new IntNumGenerate();
        int[] ints = intNumGenerate.RandomInt(5, 0, 20);
        for (int anInt : ints) {
            System.out.print(anInt+" ");
        }

        quickProcess(ints,0,4);
        System.out.println();
        for (int anInt : ints) {
            System.out.print(anInt+" ");
        }

    }









}
